SNOI2020 乱写
挑战一下今天能写完几题（ 太毒瘤了…… 咕着吧
取石子
博弈题怎么能正经做呢
$f_{i, j}$ 表示还剩 $i$ 个石子，这一步能取 $[1, j]$ 时是否有必胜策略。
$f_{i, j} = OR_{k = 1}^{j} [f_{i - k, 2k} = 0]$
设 $pos_i$ 为使得 $f_{i, j} = 1$ 的最小的 $j$。$pos$ 的表如下：
1 | 1 2 3 1 5 1 2 8 1 2 3 1 13 1 2 3 1 5 1 2 21 1 2 3 1 5 1 2 8 1 2 3 1 34 1 2 3 1 5 1 2 8 1 2 3 1 13 1 2 3 1 5 1 2 55 1 2 3 1 5 1 2 8 1 2 3 1 13 1 2 3 1 5 1 2 21 1 2 3 1 5 1 2 8 1 2 3 1 89 1 2 3 1 5 1 2 8 1 2 3 …… |
诶你发现这玩意和斐波那契数列有大大的关系！实际上我也不知道怎么看出来$pos_i$ 等于 $i$ 斐波那契进制下最低位对应的斐波那契数。可能因为 $pos_{i - pos_i} \geq 2pos_i$？
预处理 $s_{i, j}$ 表示前 $fib_i$ 项 $pos$ 中 $fib_j$ 出现的次数。$s_{i, j} = s_{i - 1, j} + s_{i - 2, j} - [j == i - 2]$，减去这个是因为 $pos_{fib_i}$ 斐波那契进制中“本”应该第 $i - 1$ 和第 $i - 2$ 位都是 $1$，但是进位了所以 $pos_{fib_i}$ 的最低位从 $i - 2$ 变成了 $i$。
$1e18$ 内的斐波那契数量是 $log$ 级别的，所以 $O(nlogn)$。
字符串
问题显然等价于排列 $a$、$b$ 使得 $\sum lcp(a_i, b_i)$ 最大。
倒插 SAM，从底向上贪心匹配。
生成树
如果原图是仙人掌显然答案等于各环大小之积。否则必然是一个大环串了很多仙人掌。
断边方式有两种：
- 断一条大环边，仙人掌上每个环各断一边
- 把一个大环上仙人掌断成两半，剩余仙人掌上环各断一边
设大环边数为 $dis$，第 $i$ 个环大小为 $siz_i$，第 $i$ 个环两半边数分别为 $l_i$、$r_i$
那么 $ans = dis \prod siz_i + ( \sum \frac{l_i * r_i}{siz_i} ) \prod siz_i$
怎么找大环边？观察发现仙人掌中度数为 $3$ 的点一定有一条邻边是大环边。出题人不讲唔得，直接令输入最后一条边为大环边……